Compiler optimization has its goal transforming code to increase its performance. One important factor in optimization is scheduling operations to increase the speed of predicated operations. The present invention relates to optimizing code executed on an Explicit Parallel Instruction Computing (EPIC) architecture and performs the global task of detecting and refining potential parallelism of the source code being compiled.
The present compiler transforms the source-code program represented as a set of Basic Blocks into Extended Scalar Blocks (ESBs) by applying a compiler technique called if-conversion. Extended Scalar Blocks are regions of the predicated code where all dependencies between operations are represented explicitly as a relation between two operations for a considerable number of operations. For each ESB the compiler works out the critical path which is defined as a sequence of operations that will take the longest CPU time and can""t be executed in parallel because of dependencies.
The problem of balancing the amount of control flow and predication at schedule time is solved in IMPACT compiler and is described in the article by David I. August, Wen-mei W. Hwu and Scott A. Mahlke, entitled xe2x80x9cA Framework for Balancing Control Flow and Predication,xe2x80x9d in Proceedings of the 30th annual IEEE/ACM International Symposium on Microarchitecture, pp. 92-103, December 1997.
According to one aspect of the invention, a compiler optimization method balances the execution time of every set of operations depending on resolution of a condition. Subsequent to removing a condition from the critical path, alternative sets of operations dependent on which value the condition resolves may have different times of termination. A conditional branch selects one of the alternatives when the condition is resolved so that if the alternative with a shorter time of termination is selected it need not wait for the lengthier part of the other alternative to terminate.
According to another aspect of the invention, the difference between the times of termination of the alternative sets of operations is compared to an algorithmic parameter to determine whether to implement the optimization procedure.
According to another aspect of the invention, if either set of operations terminates before the condition is resolved a second successor to the merge is duplicated and moved ahead of the merge to lengthen time of termination of the sets of operations.
According to another aspect of the invention, critical paths are tuned depending on predicates to supply the more exact execution timings instead of common timing of a considered region. Thus, this transformation is a correction of predicated code, obtained after if-conversion, to remove some drawbacks of concurrent execution of if-alternatives (or-parallelism).
Other features and advantages of the invention will be apparent in view of the following detailed description and appended drawings.